\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 3}

\paragraph{Задание 1.} Докажите, что в бистохастической матрице можно найти $n$ (строго) положительных элементов, никакие два из которых не стоят в одной строке или в одном столбце.
\begin{Solution}
Доказывал в предыдущем ДЗ
\end{Solution}

\paragraph{Задание 2.} На улице болтунов живут $n$ юношей и $n$ девушек, причем каждый юноша знаком ровно с $k$ девушками, а каждая девушка - ровно с $k$. Докажите, что все юноши и девушки могут одновременно говорить со своими знакомыми по телефону.
\begin{Solution}
Доказывал в предыдущем ДЗ
\end{Solution}

\paragraph{Задание 3.} Квадратный лист бумаги разбит на 100 многоугольников одинаковой площади с одной стороны и на 100 других той же площади с обратной стороны. Докажите, что этот квадрат может быть проткнут 100 иголками, чтобы каждый многоуольник был проткнут по разу.
\begin{Solution}
Построим двудольный граф следующим образом:
\begin{itemize}
\item Вершины первой доли - многоугольники лицевой стороны

\item Вершины второй доли - многоугольники оборотной стороны

\item Две вершины связаны ребром, если многоуольник лицевой и оборотной стороны пересекаются
\end{itemize}
Так как площади всех многоуольников равны, то каждый многоугольник лицевой стороны пересекается как минимум с одним многоугольником оборотной стороны, аналогичное утверждение справедливо и для произвольного количества многоугольников, таким образом условия леммы Холла выполнены, строим совершенное паросочетание. Каждое ребро такого паросочетания сопоставляется некоторой площади пересечения двух многоугольников, протыкая квадрат в этой площади получаем требуемое.
\end{Solution}

\paragraph{Задание 4. } Из шахматной доски вырезали 7 клеток. Докажите, что на оставшихся клетках можно поставить 8 не бьющих друг друга ладей

\begin{Solution}
\end{Solution}

\paragraph{Задание 5.} Даны $k$ мальчиков и $2k-1$ конфета. Докажите, что можно дать каждому мальчику по конфете так, чтобы мальчику, которомуне нравится его конфета, не нравились и конфеты остальных мальчиков.

\begin{Solution}
Доказывал в предыдущем ДЗ
\end{Solution}

\paragraph{Задание 6.} (Теорема Кенига) В некоторых клетках прямоугольной таблицы стоят звездочки. Докажите, что наибольшее количество звездочек, которые можно выбрать так, чтобы никакие две не стояли в одной строке или в одном столбце, равно наименьшему количеству линий (столбцов и строк), содержащих в объединении все звездочки.

\begin{Solution}
Сопоставим матрице двудольный граф следующим образом:
\begin{itemize}
\item Вершины первой доли - строки матрицы

\item Вершины второй доли - столбцы матрицы

\item Вершины соединены, если на пересечении столбца и строки стоит звездочка
\end{itemize}
На этом графе теорема Кенига формулируется следующим образом - наибольшее паросочетание в графе (наибольшее количество звездочек) равно наименьшему количеству вершин в покрытии графа $p$ (наименьшее количество столбцов и строк). Каждое ребро паросочетнаия содержит ка кминимум одну вершину из любого покрытия (в том числе и минимального), следовательно число вершин в покрытии не меньше числа ребер в паросочетании. Покажем что в графе существует паросочетание из $p$ ребер. Т. е. для любое $l$-подмножество вершин первой доли соединено как минимум с $l-s$ вершинами второй доли, где $s = \left|V_1\right|-p$. Предположим противное, и существует $t$-подмножество ($U$) множества $V_1$, такое что оно соединено не более чем с $t-\left|V_1\right|+p-1$ вершинами ($K$) из $V_2$. Очевидно, что множества $V_1 \setminus U \cup K$ - покрытие и его мощность $\left|V_1\right| - t + t - \left|V_1\right| + p -1 = p-1$, которое меньше минимального исходного покрытия мощности $p$, что невозможно, следовательно условие обобщенной леммы Холла выполняется и существует паросочетание мощности $p$. 

существует множество из $k$ вершин первой доли соединенное менее чем с $k-s$ вершинами второй доли, где $s$ - количество вершин ($n$) минус количество вершин в минимальном покрытии $p$, т. е. любые $k$ вершин первой доли соединены не более чем с $k-s-1 = k - n + p -1$ вершинами второй
\end{Soltuion}

\paragraph{Задание 7.} Пусть степень каждой вершины графа $G$ находится в интервале $\left[n;3n\right]$. Докажите, что для любого $k < n$, найдется подграф $H$ на тех же вершинах, что степень его вершин будет лежать в интерфале $\left[k;3k\right]$

\begin{Solution}
\end{Solution}

\paragraph{Задание 8.} Докажите реберный вариант теоремы Менгера: если $u$ и $v$ - две вершины графа $G$, то следующие условия равносильны:
\begin{itemize}
\item при удалении любых $k$ ребер можно попасть из $u$ в $v$

\item существует $k+1$ путей из $u$ в $v$ таких, что каждое ребро принадлежит не более чем одному из них.
\end{temize}

\begin{Solution}
\end{Solution}

\paragraph{Задание 9.} Докажите, что в любом связном графе с $n \ge 3$ вершинами можно обойти все вершины, пройдя в сумме не более чем по $2n-4$ ребрам.

\begin{Solution}
\end{Solution}

\paragraph{Задание 10.} Докажите, что в любом турнире есть гамильтонов путь (то есть путь, проходящий по всем вершинам ровно по разу)

\begin{Solution}
Как я понимаю граф турнира - полный граф. Нарисуем граф расположив все его вершины по коружности через равные расстояния, получаем правильный многоугольник со всеми его диагоналями, путь проходящий по контуру этого многоугольника гамильтонов, так как проходит через все вершины ровно по разу. Для любого полного однодольного графа такое расположение возможно. Кроме того, на полном графе выполняется условие Дирака, поэтому в нем есть гамильтонов путь.
\end{Solution}
\end{document}
